# -*- coding: UTF-8 -*-
"""
@author: tgy
@file: quick_sort.py
@time: 2021/03/02
"""


class Sort:
    ...

    def quick_sort(self, nums: list):
        ...
        if nums is None:
            return
        if len(nums) <= 1:
            return;
        self._do_quick_sort(nums, 0, len(nums))

    def _do_quick_sort(self, nums: list, down: int, top: int):
        ...
        # right - left 为排序范围的长度
        if down >= top:
            return

        base = nums[down]
        left = down
        right = top - 1
        while left < right:
            ...
            # 这里注意使用 <
            while left < right and base < nums[right]:
                right -= 1
            nums[left] = nums[right]
            left += 1

            # 这里注意使用 >
            while left < right and base > nums[left]:
                left += 1
            nums[right] = nums[left]
            right -= 1

        nums[left] = base
        self._do_quick_sort(nums, down, left)
        self._do_quick_sort(nums, left + 1, top)


if __name__ == '__main__':
    pass
    nums = [4, 1, 3, 5, 2, 6, 3, 4]
    sort = Sort()
    sort.quick_sort(nums)
    print(nums)
